/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-10-04
 * Time: 23:01
 */

//管理 先描述 在组织
class Node{
    //先描述
    public int data;
    public Node next;
    public Node(int data){
        this.data = data;
    }
}

//在组织
public class ListNode {
    //设置一个头节点
    private Node head;

    //穷举的方式创建一个链表
    public void createList(){
        Node node1 = new Node(20);
        Node node2 = new Node(10);
        Node node3 = new Node(30);
        Node node4 = new Node(70);
        Node node5 = new Node(10);
        Node node6 = new Node(10);


        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = null;
    }

    //遍历链表
    public void display(){
        Node cur = this.head;
        while (cur != null){
            //遍历到所有元素的时 cur != null
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //头插法
    public void addFirst(int data){
        Node node = new Node(data);
        if (this.head == null){
            this.head = node;
        }
        node.next = head;
        this.head = node;
    }
    //尾插法
    public void addLast(int data){
        //先要找到尾巴
        Node node = new Node(data);
        Node cur = this.head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if (this.head == null){
            return false;
        }
        Node cur = this.head;
        Node node = new Node(data);
        int num = index;
        while (num > 0){
            cur = cur.next;
            num--;
        }
        node.next = cur.next;
        cur.next = node;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if (this.head == null){
            return false;
        }
        Node cur = this.head;
        while (cur != null){
            if (cur.data == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (this.head.data == key){
            this.head = head.next;
        }
        Node cur = this.head;
        Node curN = null;
        while (cur != null){
            if (cur.data == key){
                curN.next = cur.next;
                return;
            }
            curN = cur;
            cur = cur.next;
        }
        System.out.println("没有你要删除的元素！");
        return;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (this.head.data == key){
            this.head = head.next;
        }
        Node cur = this.head;
        Node curN = null;
        int count = 0;
        while (cur != null){
            if (cur.data == key){
                curN.next = cur.next;
                cur = cur.next;
                count++;
                continue;
            }
            curN = cur;
            cur = cur.next;
            if (count > 0 && cur == null){
                System.out.println("删除key值" + count + "次!");
                return;
            }
        }
        System.out.println("没有你要删除的元素！");
        return;
    }


    //删除所有值为key的节点
    //定义两个指针 前后永远一前一后
    //只存在两个情况 相同 和 不相同
    public Node removeAllKey1(int key){
        if (this.head==null) return null;
        Node prev = this.head;
        Node cur = this.head.next;
        while (cur != null){
            if (cur.data == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后处理头节点
        if (this.head.data == key){
            this.head = this.head.next;
        }
        return this.head;
    }

    //得到单链表的长度
    public int size(){return -1;};
    public void clear(){};
}
